package aco;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.EnumMap;
import java.util.HashMap;
import java.util.List;



public class Master {

	/*
	 * ACO PARAMETERS
	 */
	public static final double 	BETA 				= -2d;		//parameter for city selection rule
	public static final double 	GAMMA 				= 0.1d;		//global pheromon decay parameter
	public static final double 	RHO 				= 0.1d;		//local pheromon decay parameter
	public static final int 	NUMBER_ANTS 		= 2;		//number of ants
	public static final int 	Q 					= 100;		//problem dependant constant
	public static final double	Q_0					= 0.9d;		//random parameter for city selection rule
	public static final int 	NUMBER_ITERATIONS 	= 1000;		//number of iterations
	
	private ArrayList<Ant> 		ants;							//the worker threads
	
	private int 		number_nodes;
	private double[][] 	distance_matrix;
	private double[][] 	pheromone_matrix;
	private Object[][]	mutexes;
	private double 		tau0;
	private long 		startTime;
	
	private double result_time = 0;
	private double result_cost = 0;
	
	public Master(String matrixFileName, boolean format){
		try {
			if (format) {
				readMatrixFromFile(matrixFileName);

			} else {
				readMatrixFromFile2(matrixFileName);
			}			
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public Master(String matrixFileName) {
		//get tsp file format (euc_2d or explicit)
		BufferedReader br;
		try {
			br = new BufferedReader(new FileReader(new File(matrixFileName)));
			String line;
			while((line = br.readLine()) != null){
				if(line.contains("EDGE_WEIGHT_TYPE")){
					if(line.contains("EXPLICIT")){
						readMatrixFromFile(matrixFileName);
					}else if(line.contains("EUC_2D")){
						readMatrixFromFile2(matrixFileName);
					}
				}
			}
		} catch (FileNotFoundException e1) {
			e1.printStackTrace();
		}
		catch (IOException e) {
			e.printStackTrace();
		}
	}

	private void readMatrixFromFile2(String matrixFileName) throws IOException {
		FileParser fp = new FileParser(matrixFileName);
		distance_matrix = fp.getMatrix();
		number_nodes = fp.getNumberOfNodes();
		pheromone_matrix = initMatrix(number_nodes);
		initMutexMatrix(number_nodes);		
	}
	

	public void readMatrixFromFile(String matrixFileName) throws IOException{
		//create a BufferedReader for the file
		BufferedReader br = new BufferedReader(new FileReader(new File(matrixFileName)));
		int row = 0;
		int column = 0;
		boolean processDistances = false;
		String line;
		
		while((line = br.readLine()) != null){
			if (line.equals("EOF")) {
				break;
			}
			
			else if(processDistances){
				String distances[] = line.split(" ");
				for(int i = 0; i < distances.length; i++){
					if(!distances[i].isEmpty()){
						double distance = Double.parseDouble(distances[i]);
						distance_matrix[row][column] = distance;
						distance_matrix[column][row] = distance;
						column++;
						if(distance == 0){
							row++;
							column = 0;
						}
					}
				}
			}
			else if(line.contains("DIMENSION:")){
				number_nodes= Integer.parseInt(line.substring(11));
				distance_matrix = initMatrix(number_nodes);
				pheromone_matrix = initMatrix(number_nodes);
				initMutexMatrix(number_nodes);
			}
			else if(line.contains("EDGE_WEIGHT_SECTION")){
				processDistances = true;
			}
		}
		
	}
	
	private double[][] initMatrix(int dim) {
		double matrix[][] = new double[dim][dim];
		for(int i = 0; i < matrix.length; i++){
			for(int j = 0; j < matrix[i].length; j++){
				matrix[i][j] = 0;
			}
		}
		return matrix;
	}



	public static void main(String[] args) {
		int fileNr = 0;
		//get files from folder files
		File dir = new File("files");
		HashMap<Integer, String> files = new HashMap<Integer, String>();
		for(int i = 0; i < dir.list().length; i++){
			if(dir.list()[i].endsWith(".tsp")){
				System.out.println(i + " - " + dir.list()[i]);
				files.put(i, dir.list()[i]);
			}	
		}
		try {
			String line;
		      BufferedReader is = new BufferedReader(
		        new InputStreamReader(System.in));
		      line = is.readLine();
		      fileNr = Integer.parseInt(line);
		    } catch (NumberFormatException ex) {
		    } catch (IOException e) {
		}
		Master master = new Master(dir.getName() + "/" + files.get(fileNr));
		
		
		//Master master = new Master("files/gr24.tsp", true);
		//Master master = new Master("files/berlin52.tsp", false);
		//master.printDistanceMatrix();
		master.initPheromoneMatrix();
		//master.initAnts();
		master.startAnts();
	}

	private void initMutexMatrix(int number_nodes) {
		mutexes = new Object[number_nodes][number_nodes];
		for(int i = 0; i < number_nodes; i++){
			for(int j = 0; j < number_nodes; j++){
				mutexes[i][j] = new Object();
			}
		}
		
	}

	public void startAnts() {
		initPheromoneMatrix();
		startTime = System.currentTimeMillis();
		double best_cost = Double.MAX_VALUE;
		Tour best_tour = new Tour();
		for(int count = 0; count < NUMBER_ITERATIONS; count++){
			best_cost = Double.MAX_VALUE;
			initAnts();
			//start ant threads
			for(Ant ant : ants){
				ant.start();
			}
			//wait for each thread to compute a complete tour
			for(Ant ant : ants){
				try {
					ant.join();
				} catch (InterruptedException e) {e.printStackTrace();}
			}
			
			//after all ants have completed their tour compare their costs
			for(Ant ant : ants){
				if(ant.getTourCost() <= best_cost){
					best_cost = ant.getTourCost();
					best_tour = ant.getTour();
				}
			}
			//System.out.println("ITERATION " + count +": " + best_cost);
			//perform a global pheromone update for the best tour
			for(int i = 0; i < number_nodes; i++){
				for(int j = 0; j < number_nodes; j++){
					Edge e = new Edge(i, j);
					if(best_tour.contains(e)){
						pheromone_matrix[i][j] = (1 - Master.RHO) * pheromone_matrix[i][j] + 
							Master.GAMMA * Master.Q / best_cost;
					}
					else{
						pheromone_matrix[i][j] = (1 - Master.RHO) * pheromone_matrix[i][j];
					}
				}
			}
			
			for(Ant ant : ants){
				ant.receiveGlobalPheromoneUpdate(pheromone_matrix);
			}
		}
		System.out.println("Best Cost: " + best_cost);
		//System.out.println(best_tour.toString());
		long time = System.currentTimeMillis() - startTime;
		System.out.println("Time: " + (double)time/1000);
		result_time = (double)time/1000;
		result_cost = best_cost;
	}
	
	public double getResultCost(){
		return result_cost;
	}
	
	public double getResultTime(){
		return result_time;
	}

	private void printDistanceMatrix() {
		System.out.println("Distance Matrix:");
		printMatrix(distance_matrix);
	}
	
	private void printPheromoneMatrix() {
		System.out.println("Pheromone Matrix:");
		printMatrix(pheromone_matrix);
	}
	
	private void printMatrix(double[][] matrix){
		for(int i = 0; i < matrix.length; i++){
			for(int j = 0; j < matrix[i].length; j++){
				System.out.print(matrix[i][j] + " ");
			}
			System.out.println();
		}
	}
	
	public void initPheromoneMatrix(){
		double lnn = calculateNearestNeighbourCycle();
		System.out.println("-------------------------------------");
		System.out.println("Nearest Neighbour cycle cost: " + lnn);
		System.out.println("-------------------------------------");
		
		tau0 = 1/(number_nodes*lnn);
		for(int i = 0; i < pheromone_matrix.length; i++){
			for(int j = 0; j < pheromone_matrix[i].length; j++){
				pheromone_matrix[i][j] = tau0;
			}
		}
		//printPheromoneMatrix();
	}
	
	private double calculateNearestNeighbourCycle(){
		double result = 0;
		int node = 0;
		int next;
		//list of already visited nodes
		List<Integer> visited = new ArrayList<Integer>();
	
		for(int i = 0; i < number_nodes - 1; i++){
			next = findNearestNeighbour(node, visited);
			result += distance_matrix[node][next];
			node = next;
		}
		result += distance_matrix[node][0];
		
		return result;
	}

	private int findNearestNeighbour(int node, List<Integer> visited) {
		double min = Double.MAX_VALUE;
		int minIndex = -1;
		visited.add(node);
		
		for(int i = 0; i < distance_matrix[node].length; i++){
			if(!visited.contains(i) && distance_matrix[node][i] < min){
				min = distance_matrix[node][i];
				minIndex = i;
			}
		}
		
		return minIndex;
	}
	
	public void initAnts(){
		ants = new ArrayList<Ant>();
		int nrProcessors = Runtime.getRuntime().availableProcessors();
		ArrayList<Integer> selected_cities = new ArrayList<Integer>();
		boolean insert = false;
		for(int i = 0; i < nrProcessors; i++){
			while(!insert){
				int city = (int)Math.round(Math.random()*(number_nodes-1));
				if(!selected_cities.contains(city)){
					selected_cities.add(city);
					Ant ant = new Ant(this, city, number_nodes, distance_matrix, pheromone_matrix);
					ants.add(ant);
					insert = true;
				}
			}
			insert = false;
		}
	}
	
	//this method gets called by every ant after it has selected a new city
	public void citySelected(int from, int to){
		//perform local update
		synchronized(mutexes[from][to]){
			pheromone_matrix[from][to] = (1 - Master.RHO) * pheromone_matrix[from][to] + Master.RHO * tau0; 
		}
		//broadcast pheromone update to each ant
		for (Ant ant : ants) {
			ant.updatePheromoneMatrix(from, to, pheromone_matrix[from][to]);
		}
	}

}
